DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.775

A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words

Authors: David Felber and Rafail Ostrovsky

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract

A quantile summary is a data structure that approximates to epsilon-relative error the order statistics of a much larger underlying dataset. In this paper we develop a randomized online quantile summary for the cash register data input model and comparison data domain model that uses O((1/epsilon) log(1/epsilon)) words of memory. This improves upon the previous best upper bound of O((1/epsilon) (log(1/epsilon))^(3/2)) by Agarwal et al. (PODS 2012). Further, by a lower bound of Hung and Ting (FAW 2010) no deterministic summary for the comparison model can outperform our randomized summary in terms of space complexity. Lastly, our summary has the nice property that O((1/epsilon) log(1/epsilon)) words suffice to ensure that the success probability is 1 - exp(-poly(1/epsilon)).

Cite as

David Felber and Rafail Ostrovsky. A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 775-785, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{felber_et_al:LIPIcs.APPROX-RANDOM.2015.775,
  author =	{Felber, David and Ostrovsky, Rafail},
  title =	{{A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{775--785},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.775},
  URN =		{urn:nbn:de:0030-drops-53357},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.775},
  annote =	{Keywords: order statistics, data stream, streaming algorithm}
}

Search Results

Documents authored by Felber, David

A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words

Abstract

Cite as

Thanks for your feedback!

Could not send message